package junior.DynamicProgramming动态规划;

public class Test {
    public static void main(String[] args) {
        System.out.println("开始");
        int[] nums = {11,7,2,15};
        int target = 9;
        quickSort(nums,0,3);
        System.out.println(nums);
        twoSum(nums,target);
    }

    public static void twoSum(int[] nums, int target) {
//        quickSort(nums,0,nums.length - 1);
        int n = nums.length;
        for (int i = 0,j = n-1; i < j;) {
            if (nums[i] + nums[j] > target) {
                j--;
            }
            if (nums[i] + nums[j] < target) {
                i++;
            }
            if (nums[i] + nums[j] == target) {
//                return new int[]{i, j};
                System.out.println("i:"+i);
                System.out.println("j:"+j);
                break;

            }
        }
//        System.out.println(new int[0]);
//        return new int[0];
    }
    public static void quickSort(int[] arr,int low,int high) {
        int p,i,j,temp;

        if(low >= high) {
            return;
        }
        p = arr[low];
        i = low;
        j = high;
        while(i < j) {
            while(arr[j] >= p && i < j) {
                j--;
            }
            while(arr[i] <= p && i < j) {
                i++;
            }

            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        arr[low] = arr[i];
        quickSort(arr,low,j-1);  //对左边快排
        quickSort(arr,j+1,high); //对右边快排
    }
}
